package com.muchfish.algorithm.array;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/plus-one/description/">题目：66. 加一</a>
 * <br>
 * 题目描述：
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。<br>
 * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。<br>
 * 你可以假设除了整数 0 之外，这个整数不会以零开头。<br>
 * 解题思路：<br>
 * 1.找出最长的后缀 9<br>
 * 1.1.如果数组中所有元素均为 9，则返回长度加一的数组<br>
 * 1.2.如果数组中存在不为 9 的元素，则将该元素加一，并将后续所有元素置为 0<br>
 *
 */
public class Array4 {
    public static void main(String[] args) {
        int[] nums = {9, 9};
        System.out.println(Arrays.toString(plusOne(nums)));

    }

    private static int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        // digits 中所有的元素均为 9
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }

}
